import java.util.*;

public class Main {

    public static int n;
    public static int[][] arr;
    public static int[] count;
    public static Map<Integer, List<Integer>> map = new HashMap<>(); // key 为炸弹个数，value 为路径

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        count = new int[n]; //地窖中的炸弹数
        for (int i = 0; i < n; i++) {
            count[i] = sc.nextInt();
        }

        arr = new int[n][n]; //地窖之间是否联通
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = sc.nextInt();
                    arr[j][i] = arr[i][j];
                }
            }
        }

        Map<Integer, List<Integer>> retMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map = new HashMap<>();
            boolean[] flag = new boolean[n];

            List<Integer> list = new ArrayList<>();
            dfs(i, 0, list, flag);
            List<Integer> path = new ArrayList<>();
            int sum = 0;

            //找最大的炸弹数以及对应的路径
            for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
                if (entry.getKey() > sum) {
                    sum = entry.getKey();
                    path = entry.getValue();
                }
            }

            retMap.put(sum, path);
        }

        List<Integer> path = new ArrayList<>();
        int sum = 0;

        //找最大的炸弹数以及对应的路径
        for (Map.Entry<Integer, List<Integer>> entry : retMap.entrySet()) {
            if (entry.getKey() > sum) {
                sum = entry.getKey();
                path = entry.getValue();
            }
        }

        for (int num : path) {
            System.out.print(num + " ");
        }

        System.out.println();
        System.out.println(sum);


        sc.close();
    }

    /**
     *
     * @param index 当前地窖的下标
     * @param sum 炸弹总数
     * @param list 路径
     */
    public static void dfs(int index, int sum, List<Integer> list, boolean[] flag) {
        if (!isLive(index, flag)) {
            map.put(sum, new ArrayList<>(list));
            return;
        }

        for (int j = index; j < n; j++) {
            if (!flag[j] && arr[index][j] == 1) {
                list.add(j + 1);
                flag[j] = true;
                dfs(j, sum + count[j], list, flag);

                //回溯
                list.remove(list.size() - 1);
                flag[j] = false;
            }
        }
    }

    /**
     * 查找这个地窖之后是否能走通
     * @param index
     */
    public static boolean isLive(int index, boolean[] flag) {
        for (int i = 0; i < n; i++) {
            if (!flag[i] && arr[index][i] == 1) {
                return true;
            }
        }
        return false;
    }
}
